Search Results

Documents authored by Mathieu, Claire

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.91
A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023]. In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5+ε)-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.
Cite as

Claire Mathieu and Hang Zhou. A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 91:1-91:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mathieu_et_al:LIPIcs.ICALP.2023.91,
  author =	{Mathieu, Claire and Zhou, Hang},
  title =	{{A Tight (1.5+\epsilon)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{91:1--91:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.91},
  URN =		{urn:nbn:de:0030-drops-181430},
  doi =		{10.4230/LIPIcs.ICALP.2023.91},
  annote =	{Keywords: approximation algorithms, capacitated vehicle routing, graph algorithms, combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.27
An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees

Authors: Marc Dufay, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most D. The DVRP on trees is of independent interest, because it is equivalent to the "virtual machine packing" problem on trees studied by Sindelar et al. [SPAA'11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its approximation ratio is α + ε, where α ≈ 1.691, and in addition, that our analysis is essentially tight. The running time is polynomial in n and D. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks'12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of "reduced length".
Cite as

Marc Dufay, Claire Mathieu, and Hang Zhou. An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dufay_et_al:LIPIcs.STACS.2023.27,
  author =	{Dufay, Marc and Mathieu, Claire and Zhou, Hang},
  title =	{{An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.27},
  URN =		{urn:nbn:de:0030-drops-176794},
  doi =		{10.4230/LIPIcs.STACS.2023.27},
  annote =	{Keywords: vehicle routing, distance constraint, approximation algorithms, trees}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.63
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm

Authors: Fabrizio Grandoni, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time (2+ε)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].
Cite as

Fabrizio Grandoni, Claire Mathieu, and Hang Zhou. Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grandoni_et_al:LIPIcs.ITCS.2023.63,
  author =	{Grandoni, Fabrizio and Mathieu, Claire and Zhou, Hang},
  title =	{{Unsplittable Euclidean Capacitated Vehicle Routing: A (2+\epsilon)-Approximation Algorithm}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{63:1--63:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.63},
  URN =		{urn:nbn:de:0030-drops-175660},
  doi =		{10.4230/LIPIcs.ITCS.2023.63},
  annote =	{Keywords: capacitated vehicle routing, approximation algorithms, Euclidean plane}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.95
A PTAS for Capacitated Vehicle Routing on Trees

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.
Cite as

Claire Mathieu and Hang Zhou. A PTAS for Capacitated Vehicle Routing on Trees. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mathieu_et_al:LIPIcs.ICALP.2022.95,
  author =	{Mathieu, Claire and Zhou, Hang},
  title =	{{A PTAS for Capacitated Vehicle Routing on Trees}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.95},
  URN =		{urn:nbn:de:0030-drops-164369},
  doi =		{10.4230/LIPIcs.ICALP.2022.95},
  annote =	{Keywords: approximation algorithms, capacitated vehicle routing, graph algorithms, combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.43
Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We give a probabilistic analysis of the unit-demand Euclidean capacitated vehicle routing problem in the random setting, where the input distribution consists of n unit-demand customers modeled as independent, identically distributed uniform random points in the two-dimensional plane. The objective is to visit every customer using a set of routes of minimum total length, such that each route visits at most k customers, where k is the capacity of a vehicle. All of the following results are in the random setting and hold asymptotically almost surely. The best known polynomial-time approximation for this problem is the iterated tour partitioning (ITP) algorithm, introduced in 1985 by Haimovich and Rinnooy Kan. They showed that the ITP algorithm is near-optimal when k is either o(√n) or ω(√n), and they asked whether the ITP algorithm was "also effective in the intermediate range". In this work, we show that when k = √n, the ITP algorithm is at best a (1+c₀)-approximation for some positive constant c₀. On the other hand, the approximation ratio of the ITP algorithm was known to be at most 0.995+α due to Bompadre, Dror, and Orlin, where α is the approximation ratio of an algorithm for the traveling salesman problem. In this work, we improve the upper bound on the approximation ratio of the ITP algorithm to 0.915+α. Our analysis is based on a new lower bound on the optimal cost for the metric capacitated vehicle routing problem, which may be of independent interest.
Cite as

Claire Mathieu and Hang Zhou. Probabilistic Analysis of Euclidean Capacitated Vehicle Routing. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mathieu_et_al:LIPIcs.ISAAC.2021.43,
  author =	{Mathieu, Claire and Zhou, Hang},
  title =	{{Probabilistic Analysis of Euclidean Capacitated Vehicle Routing}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.43},
  URN =		{urn:nbn:de:0030-drops-154769},
  doi =		{10.4230/LIPIcs.ISAAC.2021.43},
  annote =	{Keywords: capacitated vehicle routing, iterated tour partitioning, probabilistic analysis, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.68
A Simple Algorithm for Graph Reconstruction

Authors: Claire Mathieu and Hang Zhou

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
How efficiently can we find an unknown graph using distance queries between its vertices? We assume that the unknown graph is connected, unweighted, and has bounded degree. The goal is to find every edge in the graph. This problem admits a reconstruction algorithm based on multi-phase Voronoi-cell decomposition and using Õ(n^{3/2}) distance queries [Kannan et al., 2018]. In our work, we analyze a simple reconstruction algorithm. We show that, on random Δ-regular graphs, our algorithm uses Õ(n) distance queries. As by-products, we can reconstruct those graphs using O(log² n) queries to an all-distances oracle or Õ(n) queries to a betweenness oracle, and we bound the metric dimension of those graphs by log² n. Our reconstruction algorithm has a very simple structure, and is highly parallelizable. On general graphs of bounded degree, our reconstruction algorithm has subquadratic query complexity.
Cite as

Claire Mathieu and Hang Zhou. A Simple Algorithm for Graph Reconstruction. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mathieu_et_al:LIPIcs.ESA.2021.68,
  author =	{Mathieu, Claire and Zhou, Hang},
  title =	{{A Simple Algorithm for Graph Reconstruction}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{68:1--68:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.68},
  URN =		{urn:nbn:de:0030-drops-146496},
  doi =		{10.4230/LIPIcs.ESA.2021.68},
  annote =	{Keywords: reconstruction, network topology, random regular graphs, metric dimension}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.80
Approximating Maximum Integral Multiflows on Bounded Genus Graphs

Authors: Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.
Cite as

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen. Approximating Maximum Integral Multiflows on Bounded Genus Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 80:1-80:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2021.80,
  author =	{Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Vygen, Jens},
  title =	{{Approximating Maximum Integral Multiflows on Bounded Genus Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{80:1--80:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.80},
  URN =		{urn:nbn:de:0030-drops-141491},
  doi =		{10.4230/LIPIcs.ICALP.2021.80},
  annote =	{Keywords: Multi-commodity flows, approximation algorithms, bounded genus graphs}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.32
Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint

Authors: Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.
Cite as

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa. Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2019.32,
  author =	{Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Mitchell, Joseph S. B. and Mustafa, Nabil H.},
  title =	{{Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.32},
  URN =		{urn:nbn:de:0030-drops-112471},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.32},
  annote =	{Keywords: approximation algorithm, submodular function optimisation, unit disk graph, connectivity constraint}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.73
Covering Clients with Types and Budgets

Authors: Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, and Abhinav Srivastav

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
In this paper, we consider a variant of the facility location problem. Imagine the scenario where facilities are categorized into multiple types such as schools, hospitals, post offices, etc. and the cost of connecting a client to a facility is realized by the distance between them. Each client has a total budget on the distance she/he is willing to travel. The goal is to open the minimum number of facilities such that the aggregate distance of each client to multiple types is within her/his budget. This problem closely resembles to the set cover and r-domination problems. Here, we study this problem in different settings. Specifically, we present some positive and negative results in the general setting, where no assumption is made on the distance values. Then we show that better results can be achieved when clients and facilities lie in a metric space.
Cite as

Dimitris Fotakis, Laurent Gourvès, Claire Mathieu, and Abhinav Srivastav. Covering Clients with Types and Budgets. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 73:1-73:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.ISAAC.2018.73,
  author =	{Fotakis, Dimitris and Gourv\`{e}s, Laurent and Mathieu, Claire and Srivastav, Abhinav},
  title =	{{Covering Clients with Types and Budgets}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{73:1--73:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.73},
  URN =		{urn:nbn:de:0030-drops-100213},
  doi =		{10.4230/LIPIcs.ISAAC.2018.73},
  annote =	{Keywords: Facility Location, Geometric Set Cover, Local Search}
}
Document
DOI: 10.4230/DagRep.7.4.1
Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141)

Authors: Bodo Manthey, Claire Mathieu, Heiko Röglin, and Eli Upfal

Published in: Dagstuhl Reports, Volume 7, Issue 4 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17141 "Probabilistic Methods in the Design and Analysis of Algorithms". Probabilistic methods play a central role in theoretical computer science. They are a powerful and widely applied tool used, for example, for designing efficient randomized algorithms and for establishing various lower bounds in complexity theory. They also form the basis of frameworks like average-case and smoothed analysis, in which algorithms are analyzed beyond the classical worst-case perspective. The seminar was on probabilistic methods with a focus on the design and analysis of algorithms. The seminar helped to consolidate the research and to foster collaborations among the researchers who use probabilistic methods in different areas of the design and analysis of algorithms.
Cite as

Bodo Manthey, Claire Mathieu, Heiko Röglin, and Eli Upfal. Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141). In Dagstuhl Reports, Volume 7, Issue 4, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{manthey_et_al:DagRep.7.4.1,
  author =	{Manthey, Bodo and Mathieu, Claire and R\"{o}glin, Heiko and Upfal, Eli},
  title =	{{Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141)}},
  pages =	{1--22},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{4},
  editor =	{Manthey, Bodo and Mathieu, Claire and R\"{o}glin, Heiko and Upfal, Eli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.4.1},
  URN =		{urn:nbn:de:0030-drops-75452},
  doi =		{10.4230/DagRep.7.4.1},
  annote =	{Keywords: analysis of algorithms, average-case analysis, random graphs, randomized algorithms, smoothed analysis, sub-linear algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.8
Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs

Authors: Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Local search for combinatorial optimization problems is becoming a dominant algorithmic paradigm, with several papers using it to resolve long-standing open problems. In this paper, we prove the following `4-local' version of Hall's theorem for planar graphs: given a bipartite planar graph G = (B, R, E) such that |N(B')| >= |B'| for all |B'| <= 4, there exists a matching of size at least |B|/4 in G; furthermore this bound is tight. Besides immediately implying improved bounds for several problems studied in previous papers, we find this variant of Hall's theorem to be of independent interest in graph theory.
Cite as

Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{antunes_et_al:LIPIcs.ESA.2017.8,
  author =	{Antunes, Daniel and Mathieu, Claire and Mustafa, Nabil H.},
  title =	{{Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.8},
  URN =		{urn:nbn:de:0030-drops-78293},
  doi =		{10.4230/LIPIcs.ESA.2017.8},
  annote =	{Keywords: Planar graphs, Local search, Hall's theorem, Combinatorial optimization, Expansion}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.48
Dynamic Clustering to Minimize the Sum of Radii

Authors: Monika Henzinger, Dariusz Leniowski, and Claire Mathieu

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem.
Cite as

Monika Henzinger, Dariusz Leniowski, and Claire Mathieu. Dynamic Clustering to Minimize the Sum of Radii. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 48:1-48:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ESA.2017.48,
  author =	{Henzinger, Monika and Leniowski, Dariusz and Mathieu, Claire},
  title =	{{Dynamic Clustering to Minimize the Sum of Radii}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{48:1--48:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.48},
  URN =		{urn:nbn:de:0030-drops-78749},
  doi =		{10.4230/LIPIcs.ESA.2017.48},
  annote =	{Keywords: dynamic algorithm, clustering, approximation, doubling dimension}
}
Document
DOI: 10.4230/DagRep.6.5.94
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)

Authors: Jeff Erickson, Philip N. Klein, Dániel Marx, and Claire Mathieu

Published in: Dagstuhl Reports, Volume 6, Issue 5 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16221 “Algorithms for Optimization Problems in Planar Graphs”. The seminar was held from May 29 to June 3, 2016. This report contains abstracts for the recent developments in planar graph algorithms discussed during the seminar as well as summaries of open problems in this area of research.
Cite as

Jeff Erickson, Philip N. Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). In Dagstuhl Reports, Volume 6, Issue 5, pp. 94-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{erickson_et_al:DagRep.6.5.94,
  author =	{Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire},
  title =	{{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)}},
  pages =	{94--113},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{5},
  editor =	{Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.5.94},
  URN =		{urn:nbn:de:0030-drops-67227},
  doi =		{10.4230/DagRep.6.5.94},
  annote =	{Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016
LIPIcs, Volume 60, APPROX/RANDOM'16, Complete Volume

Authors: Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
LIPIcs, Volume 60, APPROX/RANDOM'16, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2016,
  title =	{{LIPIcs, Volume 60, APPROX/RANDOM'16, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016},
  URN =		{urn:nbn:de:0030-drops-66809},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016},
  annote =	{Keywords: Theory of Computation, Models of Computation, Modes of Computation – Online Computation, Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Numerical Algorithms and Problems – Computations on Matrices, Nonnumerical Algorithms and Problems}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.0
Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors

Authors: Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.APPROX-RANDOM.2016.0,
  author =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  title =	{{Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.0},
  URN =		{urn:nbn:de:0030-drops-66235},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.43
Carpooling in Social Networks

Authors: Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider the online carpool fairness problem of [Fagin and Williams, 1983] in which an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair. We introduce a version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d/2. For random sequences of edges from planar graph social networks we give a [deterministic] algorithm with logarithmic unfairness (holds more generally for any bounded-genus graph). This does not follow from previous random sequence results in the original model, as we show that restricting the random sequences to sparse social network graphs may increase the unfairness. A very natural class of randomized online algorithms are so-called static algorithms that preserve the same state distribution over time. Surprisingly, we show that any such algorithm has unfairness ~Theta(sqrt(d)) against oblivious adversaries. This shows that the local random greedy algorithm of [Ajtai et al, 1996] is close to optimal amongst the class of static algorithms. A natural (non-static) algorithm is global random greedy (which acts greedily and breaks ties at random). We improve the lower bound on the competitive ratio from Omega(log^{1/3}(d)) to Omega(log(d)). We also show that the competitive ratio of global random greedy against adaptive adversaries is Omega(d).
Cite as

Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach. Carpooling in Social Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fiat_et_al:LIPIcs.ICALP.2016.43,
  author =	{Fiat, Amos and Karlin, Anna R. and Koutsoupias, Elias and Mathieu, Claire and Zach, Rotem},
  title =	{{Carpooling in Social Networks}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.43},
  URN =		{urn:nbn:de:0030-drops-63234},
  doi =		{10.4230/LIPIcs.ICALP.2016.43},
  annote =	{Keywords: Online algorithms, Fairness, Randomized algorithms, Competitive ratio, Carpool problem}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.329
Effectiveness of Local Search for Geometric Optimization

Authors: Vincent Cohen-Addad and Claire Mathieu

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
What is the effectiveness of local search algorithms for geometric problems in the plane? We prove that local search with neighborhoods of magnitude 1/epsilon^c is an approximation scheme for the following problems in the Euclidean plane: TSP with random inputs, Steiner tree with random inputs, uniform facility location (with worst case inputs), and bicriteria k-median (also with worst case inputs). The randomness assumption is necessary for TSP.
Cite as

Vincent Cohen-Addad and Claire Mathieu. Effectiveness of Local Search for Geometric Optimization. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 329-344, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.SOCG.2015.329,
  author =	{Cohen-Addad, Vincent and Mathieu, Claire},
  title =	{{Effectiveness of Local Search for Geometric Optimization}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{329--344},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.329},
  URN =		{urn:nbn:de:0030-drops-51241},
  doi =		{10.4230/LIPIcs.SOCG.2015.329},
  annote =	{Keywords: Local Search, PTAS, Facility Location, k-Median, TSP, Steiner Tree}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.554
Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs

Authors: Philip N. Klein, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In correlation clustering, the input is a graph with edge-weights, where every edge is labelled either + or - according to similarity of its endpoints. The goal is to produce a partition of the vertices that disagrees with the edge labels as little as possible. In two-edge-connected augmentation, the input is a graph with edge-weights and a subset R of edges of the graph. The goal is to produce a minimum weight subset S of edges of the graph, such that for every edge in R, its endpoints are two-edge-connected in R\cup S. For planar graphs, we prove that correlation clustering reduces to two-edge-connected augmentation, and that both problems have a polynomial-time approximation scheme.
Cite as

Philip N. Klein, Claire Mathieu, and Hang Zhou. Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 554-567, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.STACS.2015.554,
  author =	{Klein, Philip N. and Mathieu, Claire and Zhou, Hang},
  title =	{{Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{554--567},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.554},
  URN =		{urn:nbn:de:0030-drops-49411},
  doi =		{10.4230/LIPIcs.STACS.2015.554},
  annote =	{Keywords: correlation clustering, two-edge-connected augmentation, polynomial-time approximation scheme, planar graphs}
}
Document
DOI: 10.4230/DagRep.3.10.36
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421)

Authors: Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu

Published in: Dagstuhl Reports, Volume 3, Issue 10 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13421 "Algorithms for Optimization Problems in Planar Graphs". The seminar was held from October 13 to October 18, 2013. This report contains abstracts for the recent developments in planar graph algorithms discussed during the seminar as well as summaries of open problems in this area of research.
Cite as

Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). In Dagstuhl Reports, Volume 3, Issue 10, pp. 36-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{borradaile_et_al:DagRep.3.10.36,
  author =	{Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire},
  title =	{{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421)}},
  pages =	{36--57},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{10},
  editor =	{Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.10.36},
  URN =		{urn:nbn:de:0030-drops-44274},
  doi =		{10.4230/DagRep.3.10.36},
  annote =	{Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization}
}
Document
DOI: 10.4230/DagSemProc.10071.3
10071 Open Problems – Scheduling

Authors: Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
Collection of the open problems presented at the scheduling seminar.
Cite as

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3,
  author =	{Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.},
  title =	{{10071 Open Problems – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3},
  URN =		{urn:nbn:de:0030-drops-25367},
  doi =		{10.4230/DagSemProc.10071.3},
  annote =	{Keywords: Open problems, scheduling}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2486
Online Correlation Clustering

Authors: Claire Mathieu, Ocan Sankur, and Warren Schudy

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We study the online clustering problem where data items arrive in an online fashion. The algorithm maintains a clustering of data items into similarity classes. Upon arrival of v, the relation between v and previously arrived items is revealed, so that for each u we are told whether v is similar to u. The algorithm can create a new luster for v and merge existing clusters. When the objective is to minimize disagreements between the clustering and the input, we prove that a natural greedy algorithm is O(n)-competitive, and this is optimal. When the objective is to maximize agreements between the clustering and the input, we prove that the greedy algorithm is .5-competitive; that no online algorithm can be better than .834-competitive; we prove that it is possible to get better than 1/2, by exhibiting a randomized algorithm with competitive ratio .5+c for a small positive fixed constant c.
Cite as

Claire Mathieu, Ocan Sankur, and Warren Schudy. Online Correlation Clustering. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 573-584, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{mathieu_et_al:LIPIcs.STACS.2010.2486,
  author =	{Mathieu, Claire and Sankur, Ocan and Schudy, Warren},
  title =	{{Online Correlation Clustering}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{573--584},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2486},
  URN =		{urn:nbn:de:0030-drops-24862},
  doi =		{10.4230/LIPIcs.STACS.2010.2486},
  annote =	{Keywords: Correlation clustering, online algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact